package sit.engreal.leetcode.problems100;

import sit.engreal.leetcode.util.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * <a href="https://leetcode.cn/problems/merge-k-sorted-lists/">23. 合并K个升序链表</a>
 */
public class LeetCode23 {
    public ListNode mergeKLists(ListNode[] lists) {
        final PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt((ListNode p) -> p.val));

        for (ListNode p : lists) {
            if (p != null) {
                queue.offer(p);
            }
        }

        final ListNode head = new ListNode();
        ListNode p = head;
        while (!queue.isEmpty()) {
            final ListNode q = queue.poll();
            if (q.next != null) {
                queue.offer(q.next);
            }
            p.next = new ListNode(q.val);
            p = p.next;
        }
        return head.next;
    }
}
